`:top

In `F33f`_`[computer science`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Computer_science]`_`f and `F33f`_`[operations research`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Operations_research]`_`f, `!exact algorithms`! are `F33f`_`[algorithms`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Algorithm]`_`f that always solve an optimization problem to optimality.

Unless `F33f`_`[P = NP`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=P_=_NP]`_`f, an exact algorithm for an `F33f`_`[NP-hard`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=NP-hardness]`_`f optimization problem cannot run in worst-case `F33f`_`[polynomial time`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Polynomial_time]`_`f. There has been extensive research on finding exact algorithms whose running time is exponential with a low base.`:cite-ref-1[`F5bf`_`[1`#cite-note-1]`_`f] `:cite-ref-2[`F5bf`_`[2`#cite-note-2]`_`f]

>>Contents

• `F0af`_`[See also`#see-also]`_`f

• `F0af`_`[References`#references]`_`f

-─

>>See also

• `F33f`_`[Approximation-preserving reduction`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Approximation-preserving_reduction]`_`f

• `F33f`_`[APX`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=APX]`_`f is the class of problems with some constant-factor approximation algorithm

• `F33f`_`[Heuristic algorithm`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Heuristic_algorithm]`_`f

• `F33f`_`[PTAS`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Polynomial-time_approximation_scheme]`_`f - a type of approximation algorithm that takes the approximation ratio as a parameter

>>References

`:cite-note-1`!1.`! `F0af`_`[↑`#cite-ref-1]`_`f `:citereffominkaski2013`aFomin, Fedor V.; Kaski, Petteri (March 2013), "Exact Exponential Algorithms", `*`F33f`_`[Communications of the ACM`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Communications_of_the_ACM]`_`f`*, `!56`! (3): 80–88, `F33f`_`[doi`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=Doi_(identifier)]`_`f:10.1145/2428556.2428575.

`:cite-note-2`!2.`! `F0af`_`[↑`#cite-ref-2]`_`f `:citereffominkratsch2010`aFomin, Fedor V.; Kratsch, Dieter (2010). `*Exact Exponential Algorithms`*. Springer. p. 203. `F33f`_`[ISBN`:/page/wikibook/entry.mu`zim=wikipedia_en_all_nopic_2025-08.zim|entry_path=ISBN_(identifier)]`_`f 978-3-642-16532-0.

`c`F0af`_`[↑ Back to top`#top]`_`f`a